import util.TreeNode;

/**
 * Created by loso on 2017/3/6.
 */

//重要
public class _530_MinimumAbsoluteDifferenceInBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);

        System.out.println(getMinimumDifference(root));
    }

    public static int getMinimumDifference(TreeNode root) {
        if (root == null){
            return Integer.MAX_VALUE/2;
        }
        int min = getmindif(root);
        int minl = getMinimumDifference(root.left);
        int minr = getMinimumDifference(root.right);

        min = Math.min(min,minl);
        min = Math.min(min,minr);

        return min;
    }

    public static int getmindif(TreeNode root){
        int r = Integer.MAX_VALUE/2;
        int l = Integer.MIN_VALUE/2;
        TreeNode ltn = root.left;
        TreeNode rtn = root.right;

        while (ltn != null){
            l = ltn.val;
            ltn = ltn.right;
        }
        while (rtn != null){
            r = rtn.val;
            rtn = rtn.left;
        }

        return Math.min(root.val - l,r - root.val);
    }

    int minDiff = Integer.MAX_VALUE;
    TreeNode prev;

    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null) minDiff = Math.min(minDiff, root.val - prev.val);
        prev = root;
        inorder(root.right);
    }
}
